<?
// <meta http-equiv="content-type" content="text/html; charset=utf-8">

function search_umls($query_string, $option)
{
	global $table_prefix;
	
	$out = "";

	global $last_idx_tmp_table;
	$last_idx_tmp_table = 0;
	
	$execute_plan = array();
	$execute_plan['operator'] = 'and';

	// MRCONSO
	$select_name = "";
	$query_where = "";

	if ( $option['query_mrconso_cui'] ) {
		$in_cui = make_query_where_in($option['query_mrconso_cui']);
		if ( $select_name ) $select_name .= " AND ";
		$select_name .= "{$option['query_mrconso_cui']}[MRCONSO.CUIs]";
		$query_where .= " and cui in ($in_cui)";
	}

	if ( $option['query_mrconso_sab'] ) {
		$in_sab = make_query_where_in($option['query_mrconso_sab']);
		if ( $select_name ) $select_name .= " AND ";
		$select_name .= "{$option['query_mrconso_sab']}[MRCONSO.SABs]";
		$query_where .= " and sab in ($in_sab)";
	}

	if ( $option['query_mrconso_str'] ) {
		$query_where_str = "";
		foreach ( explode (",", $option['query_mrconso_str']) as $s ) {
			$s = trim($s);
			if ( !$s ) continue;
			
			if ( $query_where_str ) $query_where_str .= " or ";
			$query_where_str .= "str like '$s'";
		}		
		if ( $select_name ) $select_name .= " AND ";
		$select_name .= "{$option['query_mrconso_str']}[MRCONSO.STRs]";
		$query_where .= " and ($query_where_str)";
	}

	if ( $select_name ) {
		$select_query = "select distinct cui as tmpid from MRCONSO where 1 $query_where";
		$execute_plan['operand_array'][] = array('select_name'=>$select_name, 'select_query'=>$select_query);
	}

	// MRSTY
	$select_name = "";
	$query_where = "";

	if ( $option['query_mrsty_tui'] ) {
		$in_tui = make_query_where_in($option['query_mrsty_tui']);
		if ( $select_name ) $select_name .= " AND ";
		$select_name .= "{$tui}[MRSTY.TUIs]";
		$query_where .= " and tui in ($in_tui)";
	}

	if ( $select_name ) {
		$select_query = "select distinct cui as tmpid from MRSTY where 1 $query_where";
		$execute_plan['operand_array'][] = array('select_name'=>$select_name, 'select_query'=>$select_query);
	}

	// MRHIER
	$select_name = "";
	$query_where = "";

	if ( $option['query_mrhier_sab'] ) {
		$in_sab = make_query_where_in($option['query_mrhier_sab']);
		if ( $select_name ) $select_name .= " AND ";
		$select_name .= "{$sab}[MRHIER.SABs]";
		$query_where .= " and sab in ($in_sab)";
	}
	
	if ( $option['query_mrhier_cui'] ) {
		$query_where_fcui = "";
		foreach ( explode (",", $option['query_mrhier_cui']) as $s ) {
			$s = trim($s);
			if ( !$s ) continue;

			$query = "select * from {$table_prefix}concept_tree where cui = '$s'";
			$result = mysql_query($query) or die("\n<br>Query:$query\n<br>Error:".mysql_error());
			while( $row = mysql_fetch_array($result) ) {
				$fcui = $row['fcui'];
				
				if ( $query_where_fcui ) $query_where_fcui .= " or ";
				$query_where_fcui .= "fcui like '{$fcui}%'";
			}
			mysql_free_result($result);
		}		
		if ( $select_name ) $select_name .= " AND ";
		$select_name .= "{$option['query_mrhier_cui']}[MRHIER.CUIs]";
		$query_where .= " and ($query_where_fcui)";
	}

	if ( $select_name ) {
		$select_query = "select distinct cui as tmpid from {$table_prefix}concept_tree where 1 $query_where";
		$execute_plan['operand_array'][] = array('select_name'=>$select_name, 'select_query'=>$select_query);
	}

	// run
	if ( $execute_plan['operator'] == 'and' && !$execute_plan['operand_array'] ) return "";
	$execute_plan = query_trim_execute_plan($execute_plan);
	$print_user_query = "";
	$pass = query_execute($execute_plan, "char(8)", $print_user_query);

	// print
	$query = "select count(*) from temporary_1";
	$result = mysql_query($query) or die("\n<br>Query:$query\n<br>Error:".mysql_error());
	$row = mysql_fetch_array($result);
	$cnt = $row[0];
	if ( $cnt == 0 ) return "";

	$print_user_query = query_trim_print_user_query($execute_plan, $print_user_query);
	$out .= "\n<p>User Query : {$print_user_query} ($cnt)</p>";
	if ( !$pass ) return "";

	$print_toggle = "";
	if ( $option['visible_checkbox'] ) $print_toggle = "<input type='checkbox' onClick='toggle(this)'> ";
	
	$out .= "
<script language='JavaScript'>
function toggle(source) 
{
	checkboxes = document.getElementsByName('cui_array[]');
	for each (var checkbox in checkboxes)
		checkbox.checked = source.checked;
}
</script>
<table border='0' cellpadding='5' cellspacing='1' class='simple_table'>
  <tr>
	<td>{$print_toggle}CUI</td>
	<td>STR</td>
	<td>STY</td>
  </tr>";

	$query = "select distinct a.* from temporary_1 t
							join {$table_prefix}concept a on (a.cui= t.tmpid) 
							order by a.str asc 
							limit 200";
	$result = mysql_query($query) or die("\n<br>Query:$query\n<br>Error:".mysql_error());
	while( $row = mysql_fetch_array($result) ) {
		$cui = $row['cui'];

		$print_checkbox = "";
		if ( $option['visible_checkbox'] ) $print_checkbox = "<input type='checkbox' name='cui_array[]' value='{$cui}'> ";
		$print_sty_list = str_replace("_", "<br>", $row['sty_list']);
		

		$out .= "
  <tr>
    <td valign=top>{$print_checkbox}{$cui} 
	  <a href='concept_viewer_cui.php?query_cui=$cui' title='detail'>&raquo;</a>
	  <a href='concept_viewer.php?query_table=concept_tree&query_bcui=$cui&show_rel=1' title='tree' $t_style>T</a>
	</td>
	<td valign=top>{$row['str']}</td>
	<td valign=top>{$print_sty_list}</td>
  </tr>";
	}
	$out .= "
</table>";
	return $out;		
}


function get_parent_tree($query_bcui)
{
	global $table_prefix;
	
	$where_subset = "";
	if ( $_REQUEST[query_subset] ) $where_subset = sprintf("and subset = '%s'", add_to_query($_REQUEST[query_subset]));
	
	$str_val_list = array();
	$query = "select * from {$table_prefix}{$_REQUEST[query_table]} where cui = '$query_bcui' $where_subset";
	$result = mysql_query($query) or die("\n<br>Query:$query\n<br>Error:".mysql_error());
	while( $row = mysql_fetch_array($result) ) {

		$fcui = $row['fcui'];
		$fstr = $row['fstr'];
		
		$fcui_array = explode("_", $fcui);
		$fstr_array = explode("_", $fstr);
		
		$idx = "";
		for ( $i = 0 ; $i < count($fcui_array) ; $i++ ) {
			$cui = $fcui_array[$i];
			$str = $fstr_array[$i];

			if ( $idx ) $idx .= "_";
			$idx .= $cui;
			
			$str_val_list[$idx]['cui'] = $cui;
			$str_val_list[$idx]['str'] = $str;
		}
	}

	$tree = make_tree_parse_list($str_val_list, "_");
	return $tree;
}

function make_parent_tree_html($tree)
{
	$html = "";
	
	$cui = $tree['_value']['cui'];
	$str = $tree['_value']['str'];
	
	if ( $cui ) $html .= "<a href='concept_viewer.php?query_table={$_REQUEST[query_table]}&query_subset={$_REQUEST[query_subset]}&query_bcui={$cui}' style='font-weight:normal;'>$str</a> <span style='color:#999999'>$cui</span> ";
	foreach ( $tree as $key => $val ) if ( $key != "_value" ) $has_child = true;
	if ( $has_child ) {
		$html .= "<ul>";
		foreach ( $tree as $key => $val ) {
			if ( $key == "_value" ) continue;

			$html .= "<li>";
			$html .= make_parent_tree_html($val);
			$html .= "</li>";
		}
		$html .= "</ul>";
	}
	return $html;
}


function get_sub_tree($query_bcui, $query_rcui)
{
	global $table_prefix;

	$temporary_list = array();
	$query = "select * from {$table_prefix}temporary_concept";
	$result = mysql_query($query) or die("\n<br>Query:$query\n<br>Error:".mysql_error());
	while( $row = mysql_fetch_array($result) ) {
		$cui = $row['cui'];
		$temporary_list[$cui] = true;
	}

	$query_depth = $_REQUEST[query_depth];
	if ( !$query_bcui && !$query_rcui ) $query_depth = 0;
	
	$where_subset = "";
	if ( $_REQUEST[query_subset] ) $where_subset = sprintf("and a.subset = '%s'", add_to_query($_REQUEST[query_subset]));

	$sub_str_val_list = array();
	if ( $_REQUEST[expand_type] == 9 || $_REQUEST[expand_type] == 0 ) {
		// 9:none, 0:expand

		$bfcui_depth_list = array();
		if ( $query_bcui ) {
		
			$query = "select * from {$table_prefix}{$_REQUEST[query_table]} a where a.cui = '$query_bcui' $where_subset";
			$result = mysql_query($query) or die("\n<br>Query:$query\n<br>Error:".mysql_error());
			while( $row = mysql_fetch_array($result) ) {
				$fcui = $row['fcui'];
				$bfcui_depth_list[$fcui] = $row['depth'];
			}
			
		} else {
	
			$query = "select a.*, b.str_list, b.sab_list, b.sty_list, b.ro_cnt, b.rq_cnt, b.sy_cnt from {$table_prefix}{$_REQUEST[query_table]} a join {$table_prefix}concept b on (a.cui = b.cui) where a.depth = 1 $where_subset";
			$result = mysql_query($query) or die("\n<br>Query:$query\n<br>Error:".mysql_error());
			while( $row = mysql_fetch_array($result) ) {
				$fcui = $row['fcui'];
				$bfcui_depth_list[$fcui] = $row['depth'];
			}
	
			$idx = "";
			$sub_str_val_list[$idx]['cui'] = "";
			$sub_str_val_list[$idx]['str'] = "TOP";
			$sub_str_val_list[$idx]['str_list'] = "";
			$sub_str_val_list[$idx]['sab_list'] = "";
			$sub_str_val_list[$idx]['sty_list'] = "";
			$sub_str_val_list[$idx]['ro_cnt'] = 0;
			$sub_str_val_list[$idx]['rq_cnt'] = 0;
			$sub_str_val_list[$idx]['sy_cnt'] = 0;
			$sub_str_val_list[$idx]['rcui'] = "";
			$sub_str_val_list[$idx]['child_cnt'] = 0;
			$sub_str_val_list[$idx]['node_child_cnt'] = 0;
			$sub_str_val_list[$idx]['temporary'] = 0;
		}
		
		foreach ( $bfcui_depth_list as $bfcui => $depth ) {
			$sfcui = substr($bfcui, 0, -8);						
			if ( $query_rcui ) $sfcui .= $query_rcui;			
			
			$rdepth = substr_count($query_rcui, "_");	
			$max_depth = $depth+$rdepth+$query_depth;

			if ( $_REQUEST[expand_type] == 9 ) 
				$query = "select a.fcui, a.child_cnt as node_child_cnt, b.* 
							from {$table_prefix}{$_REQUEST[query_table]} a join {$table_prefix}concept b on (a.cui = b.cui) 
							where a.fcui = '{$sfcui}' $where_subset";
			else 
				$query = "select a.fcui, a.child_cnt as node_child_cnt, b.* 
							from {$table_prefix}{$_REQUEST[query_table]} a join {$table_prefix}concept b on (a.cui = b.cui) 
							where a.fcui like '{$sfcui}%%' and a.depth <= '$max_depth' $where_subset order by a.depth asc, a.str asc limit {$_REQUEST[query_limit]}";
	
			$result = mysql_query($query) or die("\n<br>Query:$query\n<br>Error:".mysql_error());
			while ( $row = mysql_fetch_array($result) ) {
				$fcui = $row['fcui'];							
				$cui = $row['cui'];
	
				$idx = substr($fcui, strlen($sfcui)+1);
				if ( !$idx ) $idx = ""; 
				
				$rcui = substr($fcui, strlen($bfcui)-8);		
				if ( $rcui[0] == '|' ) $rcui = substr($rcui, 1);
				
				if ( !$sub_str_val_list[$idx] || ($sub_str_val_list[$idx]['node_child_cnt'] < $row['node_child_cnt']) ) {
					$sub_str_val_list[$idx] = $row;
					$sub_str_val_list[$idx]['rcui'] = $rcui;
					$sub_str_val_list[$idx]['temporary'] = $temporary_list[$cui];
				}
			}
		}

	} else if ( $_REQUEST[expand_type] == 1 ) {
		// full expand  

		$cui1 = substr($query_rcui, -8);
		
		$bfcui_depth_list = array();
		$query = "select * from {$table_prefix}{$_REQUEST[query_table]} a where a.cui = '$cui1' $where_subset";
		$result = mysql_query($query) or die("\n<br>Query:$query\n<br>Error:".mysql_error());
		while( $row = mysql_fetch_array($result) ) {
			$fcui = $row['fcui'];
			$bfcui_depth_list[$fcui] = $row['depth'];
		}
		
		foreach ( $bfcui_depth_list as $bfcui => $depth ) {

			$max_depth = $depth+$query_depth;
			$query = "select a.fcui, a.child_cnt as node_child_cnt, b.* 
						from {$table_prefix}{$_REQUEST[query_table]} a join {$table_prefix}concept b on (a.cui = b.cui) 
						where a.fcui like '{$bfcui}%%' and a.depth <= '$max_depth' $where_subset order by a.depth asc, a.str asc limit {$_REQUEST[query_limit]}";
	
			$result = mysql_query($query) or die("\n<br>Query:$query\n<br>Error:".mysql_error());
			while ( $row = mysql_fetch_array($result) ) {
				$fcui = $row['fcui'];							
				$cui = $row['cui'];
	
				$idx = substr($fcui, strlen($bfcui)+1);
				if ( !$idx ) $idx = ""; 
				
				$rcui = substr($fcui, strlen($bfcui)-8);		
				if ( $rcui[0] == '|' ) $rcui = substr($rcui, 1);
				
				if ( !$sub_str_val_list[$idx] || ($sub_str_val_list[$idx]['node_child_cnt'] < $row['node_child_cnt']) ) {
					$sub_str_val_list[$idx] = $row;
					$sub_str_val_list[$idx]['rcui'] = $rcui;
					$sub_str_val_list[$idx]['temporary'] = $temporary_list[$cui];
				}
			}
		}
		$sub_str_val_list[""]['node_child_cnt'] = -1;

	} else if ( $_REQUEST[expand_type] > 1 ) {
		// RO, RQ, SY

		$bfcui_depth_list = array();
		$query = "select * from {$table_prefix}{$_REQUEST[query_table]} a where a.cui = '$query_bcui' $where_subset";
		$result = mysql_query($query) or die("\n<br>Query:$query\n<br>Error:".mysql_error());
		while( $row = mysql_fetch_array($result) ) {
			$fcui = $row['fcui'];
			$bfcui_depth_list[$fcui] = $row['depth'];
		}
			
		foreach ( $bfcui_depth_list as $bfcui => $depth ) {
			$sfcui = substr($bfcui, 0, -8);						
			if ( $query_rcui ) $sfcui .= $query_rcui;			
			
			$rdepth = substr_count($query_rcui, "_");	
			$max_depth = $depth+$rdepth+$query_depth;

			$query = "select a.fcui, a.child_cnt as node_child_cnt, b.* 
						from {$table_prefix}{$_REQUEST[query_table]} a join {$table_prefix}concept b on (a.cui = b.cui) 
						where a.fcui like '{$sfcui}%%' and a.depth <= '$max_depth' $where_subset order by a.depth asc, a.str asc limit {$_REQUEST[query_limit]}";
	
			$result = mysql_query($query) or die("\n<br>Query:$query\n<br>Error:".mysql_error());
			while ( $row = mysql_fetch_array($result) ) {
				$fcui = $row['fcui'];							
				$cui = $row['cui'];
	
				$idx = substr($fcui, strlen($sfcui)+1);
				if ( !$idx ) $idx = ""; 
				
				$rcui = substr($fcui, strlen($bfcui)-8);		
				if ( $rcui[0] == '|' ) $rcui = substr($rcui, 1);
				
				if ( !$sub_str_val_list[$idx] || ($sub_str_val_list[$idx]['node_child_cnt'] < $row['node_child_cnt']) ) {
					$sub_str_val_list[$idx] = $row;
					$sub_str_val_list[$idx]['rcui'] = $rcui;
					$sub_str_val_list[$idx]['temporary'] = $temporary_list[$cui];
				}
			}
		}
	
		if ( $_REQUEST[expand_type] == 2 ) $rel = "RO";
		else if ( $_REQUEST[expand_type] == 3 ) $rel = "RQ";
		else if ( $_REQUEST[expand_type] == 4 ) $rel = "SY";
		$cui1 = substr($query_rcui, -8);
		$query = "select a.cui2, b.*
					from MRREL a join {$table_prefix}concept b on (a.cui2 = b.cui) 
					where a.rel = '{$rel}' and a.cui1 = '{$cui1}' order by b.str asc limit {$_REQUEST[query_limit]}";
		$result = mysql_query($query) or die("\n<br>Query:$query\n<br>Error:".mysql_error());
		for ( $cnt = 0 ; $row = mysql_fetch_array($result) ; $cnt++ ) {
			$cui2 = $row['cui2'];							

			$idx = $cui2;

			$rcui = $query_rcui;
			if ( $rcui ) $rcui .= "_";
			$rcui .= $cui2;
			
			if ( !isset($sub_str_val_list[$idx]) ) {
				$sub_str_val_list[$idx] = $row;
				$sub_str_val_list[$idx]['rcui'] = $rcui;
				$sub_str_val_list[$idx]['ro_cnt'] = 0;
				$sub_str_val_list[$idx]['rq_cnt'] = 0;
				$sub_str_val_list[$idx]['sy_cnt'] = 0;
				$sub_str_val_list[$idx]['child_cnt'] = 0;
				$sub_str_val_list[$idx]['node_child_cnt'] = 0;
				$sub_str_val_list[$idx]['temporary'] = $temporary_list[$cui2];
			}
		}
	}

	$sub_tree = make_tree_parse_list($sub_str_val_list, "_");
	return $sub_tree;
}

function make_sub_tree_html($tree, $first_call)
{
	// node.innerHTML = node.innerHTML + "<ul id='"+ex_id+"' name='"+ex_name+"'></ul>";
	// ex_node.innerHTML = ex_node.innerHTML + "<li id='"+c_id+"' name='"+c_name+"'>"+c_str+"</li>";
	$html = "";
	
	$id = $tree['_value']['rcui'];
	$name = $tree['_value']['cui'];
	$str = $tree['_value']['str'];
	$str_list = $tree['_value']['str_list'];
	$sab_list = $tree['_value']['sab_list'];
	$sty_list = $tree['_value']['sty_list'];
	$ro_cnt = $tree['_value']['ro_cnt'];
	$rq_cnt = $tree['_value']['rq_cnt'];
	$sy_cnt = $tree['_value']['sy_cnt'];
	$child_cnt = $tree['_value']['child_cnt'];
	$node_child_cnt = $tree['_value']['node_child_cnt'];
	$temporary = $tree['_value']['temporary'];
	$tag = $tree['_value']['tag'];
	$ex_id = $id+"e";
	$ex_name = $name+"e";
	$link  = "";

	foreach ( $tree as $key => $val ) if ( $key != "_value" ) $has_child = true;

	$print_img = "";
	if ( $node_child_cnt != 0 ) {
		if ( $has_child ) $print_img = "<img src=icon_min.gif onClick='tree_expand(this,9)' style='margin: 0px 7px 0px -18px; vertical-align:text-bottom;'>";
		else  $print_img = "<img src=icon_max.gif onClick='tree_expand(this,0)' style='margin: 0px 7px 0px -18px; vertical-align:text-bottom;'>";
	}
	
	$print_expand = "";
	$style = "color:#999999";

	$print_child_cnt = "";
	$style_text_decoration = "";
	if ( $child_cnt || $node_child_cnt != 0 ) {
		$print_child_cnt .= "<span style='{$style}'>(";
		if ( $node_child_cnt == '-1' ) {
			$print_child_cnt .= "<span class='clickable' onClick='tree_expand(this,0)' title='tree base is changed at this point'><strong>TOP</strong></span>";
			$style_text_decoration = "text-decoration:underline;";
		} else {
			$print_child_cnt .= "<span class='clickable' onClick='tree_expand(this,0)' title='current child count'>".number_format($node_child_cnt, 0, '.', ",")."</span>";
		}
		$print_child_cnt .= "/";
		$print_child_cnt .= "<span class='clickable' onClick='tree_expand(this,1)' title='all child count'>".number_format($child_cnt, 0, '.', ",")."</span>";
		$print_child_cnt .= ")</span>";
	}

	$print_rel = "";
	$print_rel .= "<span class='show_rel'>";
	if ( $ro_cnt ) $print_rel .= " <span class='clickable' onClick='tree_expand(this,2)' title='has relationship other than synonymous, narrower, or broader'>+".number_format($ro_cnt, 0, '.', ",")."RO</span>";
	if ( $rq_cnt ) $print_rel .= " <span class='clickable' onClick='tree_expand(this,3)' title='related and possibly synonymous'>+".number_format($rq_cnt, 0, '.', ",")."RQ</span>";
	if ( $sy_cnt ) $print_rel .= " <span class='clickable' onClick='tree_expand(this,4)' title='source asserted synonymy'>+".number_format($sy_cnt, 0, '.', ",")."SY</span>";
	$print_rel .= "</span>";
	
	$print_show = "";
	if ( $sab_list ) {
		$print_show .= "<span class='show_sab'>";
		if ( $print_show ) $print_show .= " / ";
		$print_show .= str_replace("_", ", ", $sab_list);
		$print_show .= "</span>";
	}
	if ( $sty_list ) {
		$print_show .= "<span class='show_sty'>";
		if ( $print_show ) $print_show .= " / ";
		$print_show .= str_replace("_", ", ", $sty_list);
		$print_show .= "</span>";
	}
	if ( $str_list ) {
		$print_s = "";		
		foreach ( explode("_", $str_list) as $s ) {
			if ( $s == $str ) continue;
			if ( $print_s ) $print_s .= ", ";
			$print_s .= $s;
		}

		$print_show .= "<span class='show_str'>";
		if ( $print_show ) $print_show .= " / ";
		$print_show .= $print_s;
		$print_show .= "</span>";
	}
	if ( $name ) {
		$print_show .= "<span class='show_cui'>";
		if ( $print_show ) $print_show .= " / ";
		$print_show .= $name;
		$print_show .= "<a href='concept_viewer_cui.php?query_cui=$name'>&raquo;</a>";
		$print_show .= "</span>";
	}

	$print_rel_show = $print_rel.$print_show;
	if ( $print_rel_show ) $print_rel_show = "<span style='{$style}'>$print_rel_show</span>";

	$style = $style_text_decoration;
	if ( $temporary ) $style .= "font-weight:bold;";
	
	// script 내에서 "를 사용하면 error 발생
	if ( $str ) $html = "$print_img<span id='{$id}|str' style='$style'>$str</span> $print_child_cnt $print_rel_show ";
	else $html = "";
	if ( $has_child ) {
		$print_event = "";
		if ( $first_call ) $print_event = " onClick='tree_on_click(event)' onDblClick='tree_on_dbl_click(event)'";
		$html .= "<ul id='$ex_id' name='$ex_name' $print_event>";
		foreach ( $tree as $key => $val ) {
			if ( $key == "_value" ) continue;
			$_value = $val["_value"];

			$id = $_value['rcui'];
			$name = $_value['cui'];

			if ( $id == "" ) $id = "TOP";
			
			$html .= "<li id='$id' name='$name'>";
			$html .= make_sub_tree_html($val, false);
			$html .= "</li>";
		}
		$html .= "</ul>";
	}
	return $html;
}




// [설  명] tree connection을 만드는 node를 찾아 낸다. 서로다른 terminal CUI가 있어야 한다
// [사용예] find_connective_concept("", $tree, 0);
function find_connective_concept($key, $tree, $depth)
{
	$prcui_list = array();

	$have_connection = false;
	$have_sub = false;										
	foreach ( $tree as $sub_key => $sub_tree ) {
		if ( $sub_key == "_value" ) continue;
		
		$sub_prcui_list = find_connective_concept($sub_key, $sub_tree, $depth+1);
		$prcui_list = array_merge($prcui_list, $sub_prcui_list);	

		if ( count($sub_prcui_list) < count($prcui_list) ) $have_connection = true;
		if ( $depth == 1 ) $have_connection = true;
		$have_sub = true;
	}

	if ( $have_connection && $key ) {
		$tmp_list = $prcui_list;
		$prcui_list = array(); 
		foreach ( $tmp_list as $sub_prcui => $val ) {
			$prcui = "{$key}|{$sub_prcui}";
			$prcui_list[$prcui] = true;
		}
	}
	if ( !$have_sub && $key ) $prcui_list[$key] = true;
	
	return $prcui_list;
}


// [설  명] cycle을 찾아낸다.
// [사용예] find_cycle_list($child_rel_list, $prev_list, $cur, $cycle_list, $done_list)
function find_cycle_list(&$child_rel_list, $prev_list, $cur, &$cycle_list, &$done_list)
{
	
	if ( $prev_list[$cur] ) {
		// cycle이 있다
	
		$cycle_node_list = array();
		$found = false;
		foreach ( $prev_list as $cui => $val ) {
			if ( $cui == $cur ) $found = true;
			if ( $found ) $cycle_node_list[$cui] = count($child_rel_list[$cui]);
		}
		
		// 자식개수가 적은 것을 찾는다
		arsort($cycle_node_list);
		
		$cycle_node_str = "";
		foreach ( $cycle_node_list as $cui => $cnt ) {
			if ( $cycle_node_str ) $cycle_node_str .= "_";
			$cycle_node_str .= $cui;
		}
		$cycle_list[$cycle_node_str] = true;
		
	} else {

		$prev_list[$cur] = true;
		if ( $child_rel_list[$cur] ) {
			foreach ( $child_rel_list[$cur] as $cui => $val ) {
				if ( $done_list[$cui] ) continue;
				find_cycle_list($child_rel_list, $prev_list, $cui, $cycle_list, $done_list);
			}
		}
		$done_list[$cur] = true;
	}
}

// [설  명] child의 개수를 update한다
// [사용예] update_child_cnt("", "", $tree, $child_cnt_list);
function update_child_cnt($idx, $key, $tree, &$child_cnt_list)
{
	$cui_list = array();
	foreach ( $tree as $sub_key => $sub_tree ) {
		if ( $sub_key == "_value" ) continue;
		
		$sub_idx = $idx;
		if ( $sub_idx ) $sub_idx .= "_";
		$sub_idx .= $sub_key;

		$sub_cui_list = update_child_cnt($sub_idx, $sub_key, $sub_tree, $child_cnt_list);
		$cui_list = array_merge($cui_list, $sub_cui_list);
	}
	$child_cnt_list[$idx] = count($cui_list);
	
	$cui_list[$key] = true;
	return $cui_list;
}

// [설  명] 계층구조를 생성한다. 최적의 tree를 생성한다
// [사용예] $tree = make_optimized_hierarchy(&$child_rel_list);
function make_optimized_hierarchy(&$child_rel_list)
{
	$parent_child_list = array();
	$child_parent_list = array();
	$all_node_list = array();
	foreach ( $child_rel_list as $cui1 => $val1 ) {
		foreach ( $val1 as $cui2 => $val2 ) {
			if ( !$val2 ) continue;
			$parent_child_list[$cui1][$cui2] = true;
			$child_parent_list[$cui2][$cui1] = true;
			$all_node_list[$cui1] = true;
			$all_node_list[$cui2] = true;
		}
	}
	foreach ( $all_node_list as $cui => $val ) {
		if ( !$parent_child_list[$cui] ) $parent_child_list[$cui] = array();
		if ( !$child_parent_list[$cui] ) $child_parent_list[$cui] = array();
	}
	
	$need_list = $parent_child_list;
	$own_list = $parent_child_list;
	$own_tree = $parent_child_list;

	$active_node_array = array();
	foreach ( $parent_child_list as $cui1 => $val1 ) {
		if ( !count($val1) ) $active_node_array[] = $cui1;
	}
	
	
	$top_node_array = array();
	foreach ( $child_parent_list as $cui2 => $val2 ) {
		if ( !count($val2) ) $top_node_array[] = $cui2;
	}
	
	$done_list = array();
	while ( count($active_node_array) ) {
	
		// active_node_array에 따라서 parent를 update한다
		foreach ( $active_node_array as $active_node ) {

			// 부모에 가서 need_list, own_list, own_tree를 수정한다
			foreach ( $child_parent_list[$active_node] as $cui1 => $val1 ) {
				
				// need_list, own_list
				foreach ( $own_list[$active_node] as $cui2 => $val2 ) {
					if ( $need_list[$cui1][$cui2] ) $need_list[$cui1][$cui2] = false;				// 있다면 false로
					$own_list[$cui1][$cui2] = true;													// 무조건 있다고 표시
				}
				if ( $need_list[$cui1][$active_node] ) $need_list[$cui1][$active_node] = false;		// 있다면 false로
				
				// own_tree
				$new_own_tree = array();
				foreach ( $own_tree[$cui1] as $sub_key => $sub_tree ) {
					if ( $sub_key == $active_node ) $new_own_tree[$sub_key] = $own_tree[$active_node];
					else if ( $own_list[$active_node][$sub_key] ) true;
					else $new_own_tree[$sub_key] = $sub_tree;
				}
				$own_tree[$cui1] = $new_own_tree;
			}
		}
		
		// active_node_array를 새로 구한다
		$new_active_node_list = array();
		foreach ( $active_node_array as $active_node ) {

			// 기존의 것은 처리할것을 모두 완료했으므로 더이상 하지 않는다
			$done_list[$active_node] = true;

			// 부모에 가서 need_list를 모두 만족하는지 테스트 한다
			foreach ( $child_parent_list[$active_node] as $cui1 => $val1 ) {
			
				$pass = true;
				foreach ( $need_list[$cui1] as $cui2 => $val2 ) if ( $val2 ) $pass = false;
				
				if ( $pass ) $new_active_node_list[$cui1] = true;
			}
		}
		$active_node_array = array_keys($new_active_node_list);
		
	}
	
	$whole_tree = array();
	foreach ( $top_node_array as $cui ) {
		$whole_tree[$cui] = $own_tree[$cui];
	}

	return $whole_tree;
}